/**
 *  @file kruskal.c
 *  @brief implementation of Kruskal's MST algorithm, using the
 *	detailed algorithm of Cormen, Leiserson, and Rivest (Introduction to
 *	Algorithms, first edition, p. 569)
 * @author Josh Blomberg @date 2005 
 * <br>$Id: kruskal.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 2005  Josh Blomberg, Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include <stdio.h>
#include "Gdr.h"

int p[MAX_VERTEX]; /* the predecessor of the vertex */
int r[MAX_VERTEX]; /* the rank of the vertex */

 /* declarations and macros for the animation */
#define MSG_SIZE 100 /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin; /* window for user prompts */
#define XW 1        /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
				   hide_window(pwin))
#define COUNT 4


int weight(edge e)
{
	int iWeight;
	sscanf(edge_label(e), "%d", &iWeight);
	return iWeight;
}


//
// utilities for disjoint set forests, from CLRS 2nd Edition, page 508
//
void MAKE_SET(vertex x)
{
	p[x] = x;
	r[x] = 0;
}

void LINK(vertex x, vertex y)
{
	if (r[x] > r[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if (r[x] == r[y])
		{
			r[y]++;
		}
	}
}
vertex FIND_SET(vertex x)
{
	if (x != p[x])
	{
		p[x] = FIND_SET(p[x]);
	}
	return p[x];
}

void UNION(vertex x, vertex y)
{
	LINK(FIND_SET(x), FIND_SET(y));
}


//
// structure and compare method used to sort edges using qsort
//
typedef struct edge_list_entry
{
	edge e;
	int w;
} EDGE_LIST_ENTRY;

int CompareEdges(const void* pa, const void* pb)
{
	EDGE_LIST_ENTRY a = *(EDGE_LIST_ENTRY*)(pa);
	EDGE_LIST_ENTRY b = *(EDGE_LIST_ENTRY*)(pb);

	if (a.w < b.w)
	{
		return -1;
	}
	else if (a.w == b.w)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}


void MST_KRUSKAL()
{
	int iEdgeCount = 0;
	EDGE_LIST_ENTRY edge_list[MAX_VERTEX * MAX_VERTEX];

	edge e;
	vertex u;
	vertex h;
	vertex t;
	int iNdx;

	// copy edges into structure for qsort
	for_all_edges(e)
	{
		edge_list[iEdgeCount].e = e;
		edge_list[iEdgeCount].w = weight(e);
		iEdgeCount++;
	}

	// initialize each vertex
	for_all_vertices(u)
	{
		MAKE_SET(u);
	}

	// sort the edges
	qsort(edge_list, iEdgeCount, sizeof(EDGE_LIST_ENTRY), CompareEdges);

	// iterate over the sorted edges
	for (iNdx=0; iNdx < iEdgeCount; iNdx++)
	{
		// show each edge as its being considered 
		blink_edge(edge_list[iNdx].e, COUNT);

		// extract the vertices from each edge
		h = head(edge_list[iNdx].e);
		t = tail(edge_list[iNdx].e);

		// if the vertices arent part of the same set
		if (FIND_SET(h) != FIND_SET(t))
		{
			// add the edge to the MST
			highlight_edge(edge_list[iNdx].e);	
			sprintf(msg, "Adding edge from %d to %d", h, t);
			wait(msg);
			UNION(h, t);
		}
		else
		{
			un_highlight_vertex(h);
			un_highlight_vertex(t);
			sprintf(msg, "Vertices %d and %d are\nalready connected", h, t);
			wait(msg);
			highlight_vertex(h);
			highlight_vertex(t);
		}
	}
}


void animat(void)
{
  	vertex u;
  	edge e;
	int iTotalWeight = 0;

  	for_all_vertices(u) 
	{
    	highlight_vertex(u);
  	}

  	init_prompt_window;

  	wait("Click RESUME to start MST KRUSKAL");

	MST_KRUSKAL();

	for_all_edges(e)
	{
		if (is_highlighted_edge(e))
		{
			iTotalWeight += weight(e);
		}
	}

	sprintf(msg, "End of MST KRUSKAL\nThe MST's total weight is: %d\nClick RESUME to exit animation", iTotalWeight);
	wait(msg);

  	for_all_vertices(u) 
	{
    	highlight_vertex(u);
  	}
  	for_all_edges(e) 
	{
    	un_highlight_edge(e);
  	}

  	destroy_prompt_window;
}



/*  [Last modified: 2007 06 28 at 19:48:02 GMT] */
